# 请实现两个函数，分别用来序列化和反序列化二叉树。

# 来源：力扣（LeetCode）
# https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/
from collections import deque


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


# 层序遍历
class Codec:
    def serialize(self, root):
        if not root:
            return None

        res = []
        queue = deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            if node:
                res.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                res.append("#")
        return res

        # res = [str(root.val) + "_"]
        # while queue:
        #     node = queue.popleft()
        #     if node.left:
        #         queue.append(node.left)
        #         res.append(str(node.left.val) + "_")
        #     else:
        #         res.append("#_")
        #     if node.right:
        #         queue.append(node.right)
        #         res.append(str(node.right.val) + "_")
        #     else:
        #         res.append("#_")
        # return "".join(res)

    def deserialize(self, data):
        if not data:
            return None
        data = data.split("_")[:-1]
        value = data.pop(0)
        root = self.generate_node(value)
        queue = [root]
        while queue:
            node = queue.pop(0)
            node.left = self.generate_node(data.pop(0))
            node.right = self.generate_node(data.pop(0))
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        return root

    def generate_node(self, s):
        if s == "#":
            return None
        return TreeNode(int(s))


# 先序
class Codec1:
    def serialize(self, root):
        if not root:
            return None

        def recur(node):
            if not node:
                return "#_"
            res = str(node.val) + "_"
            res += recur(node.left)
            res += recur(node.right)

            return res

        return recur(root)

    def deserialize(self, data):
        if not data:
            return None

        def build(lst):
            s = lst.pop(0)
            if s == "#":
                return None
            root = self.generate_node(s)
            root.left = build(lst)
            root.right = build(lst)
            return root

        data = data.split("_")[:-1]
        return build(data)

    def generate_node(self, s):
        if s == "#":
            return None
        return TreeNode(int(s))

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

